/**
 * @Author: linzp
 * @Date: 2021/12/10/11:53
 */
public class solution73_3 {
}

/**
 * 221. 最大正方形
 * 在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
 *
 *
 */
class Solution221 {
    public int maximalSquare(char[][] matrix) {
        int row = matrix.length, col = matrix[0].length;
        int maxlength = Integer.MIN_VALUE;//记录最长长度
        //初始化 相当于已经预处理新增第一行、第一列均为0
        int[][] dp = new int[row + 1][col + 1];//+1就会多一层row=0 || col=0 时 ，dp[][] = 0的状态
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == '1') {//以当前格子为右下角的正方形的最大的正方形的边长
                    dp[i + 1][j + 1] = Math.min(Math.min(dp[i][j], dp[i + 1][j]), dp[i][j + 1]) + 1;//dp[i+1][j+1]对应mtrix的格子所以+1，选出左上，左，上中的最小的正方形，因为能组成的正方形多大是看最小的那个的，可以几个正方形拼在一起会想象缺了一角的感觉
                }
                maxlength = Math.max(dp[i + 1][j + 1], maxlength);
            }
        }
        return maxlength * maxlength;
    }
}

//遍历次数是一样的，但是设置的值不一样而已，不过对应的matrix中的位置是一样的
//dp[i+1][j+1]对应mtrix的格子所以+1 这是上面的
//看看有什么不一样，
class Solution221_2 {
    public static void main(String[] args) {

    }
    public int maximalSquare(char[][] matrix) {
        /**
         dp[i][j]表示以第i行第j列为右下角所能构成的最大正方形边长, 则递推式为:
         dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]);
         **/
        int m = matrix.length;
        if(m < 1) return 0;
        int n = matrix[0].length;
        int max = 0;
        int[][] dp = new int[m+1][n+1];

        for(int i = 1; i <= m; ++i) {
            for(int j = 1; j <= n; ++j) {
                if(matrix[i-1][j-1] == '1') {
                    dp[i][j] = 1 + Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]));
                    max = Math.max(max, dp[i][j]);
                }
            }
        }

        return max*max;
    }
}